package array

import "sort"

type Pos struct {
	Value int
	Pos   int
}

type PosSlice []Pos

func (s PosSlice) Len() int           { return len(s) }
func (s PosSlice) Less(i, j int) bool { return s[i].Value < s[j].Value }
func (s PosSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

// sort 需要实现 Len、Less、Swap 三个方法

// https://leetcode-cn.com/problems/two-sum/
// 两数相加，满足目标和
// 算法: 数组遍历
// 时间复杂度: O(n)
func TwoSum(nums []int, target int) []int {
	emptySlice := []int{}
	for 0 == len(nums) {
		return emptySlice
	}

	posArr := make(PosSlice, len(nums))
	for index, currentNum := range nums {
		currentPos := Pos{currentNum, index}
		posArr[index] = currentPos
	}
	sort.Sort(posArr)

	// intSlice := sort.IntSlice(nums)
	// intSlice.Sort()

	start, end := 0, len(posArr)-1
	var currentSum int
	for start < end {
		currentSum = posArr[start].Value + posArr[end].Value
		if currentSum == target {
			return []int{posArr[start].Pos, posArr[end].Pos}
		} else if currentSum < target {
			start++
		} else {
			end--
		}
	}
	return emptySlice
}
